package euler.p051_100;

import euler.MainEuler;

public class Euler087 extends MainEuler {

    /*
        The smallest number expressible as the sum of a prime square,
        prime cube, and prime fourth power is 28.
        In fact, there are exactly four numbers below fifty
        that can be expressed in such a way:

        28 = 2^2 + 2^3 + 2^4
        33 = 3^2 + 2^3 + 2^4
        49 = 5^2 + 2^3 + 2^4
        47 = 2^2 + 3^3 + 2^4

        How many numbers below fifty million can be expressed
        as the sum of a prime square, prime cube, and prime fourth power?

     */
    public String resolve() {

        int limite = 50000000;

        boolean[] array = new boolean[limite+1];
        double maxI = Math.pow(limite - 12, (float)1/4);
        for (int i = 2; i <= maxI; i++) {
            if (primeHelper.isPrime(i)) {
                int fourthpower = i*i*i*i;
                double maxJ = Math.pow(limite - fourthpower - 4, (float)1/3);
                for (int j = 2; j <= maxJ; j++) {
                    if (primeHelper.isPrime(j)) {
                        int cube = j*j*j;
                        double maxK = Math.sqrt(limite - cube - fourthpower);
                        for (int k = 2; k <= maxK; k++) {
                            if (primeHelper.isPrime(k)) {
                                array[fourthpower + cube + k*k] = true;
                            }
                        }
                    }
                }
            }
        }

        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i]) {
                count++;
            }
        }

        return String.valueOf(count);
    }
}
